package com.tanzc.sort;

import com.tanzc.util.ArrayUtils;

import java.util.Date;

/**
 * <p> description: 希尔排序</p>
 *
 * @author tanzc
 * @date 2021/12/28
 **/
public class ShellSort {
    public static void main(String[] args) {
        ShellSort shellSort = new ShellSort();
        int num = 10000000, max = num * 5;
        int[] arr = ArrayUtils.random(num, max);
//        int[] arr = ArrayUtils.worst(num);
//        int[] arr = ArrayUtils.bad(num);
//        int[] arr = ArrayUtils.nice(num);

        int[] arr1 = new int[num];
        System.arraycopy(arr, 0, arr1, 0, num);
//        ArrayUtils.printArray(arr1);

        System.out.print("希尔排序-----time: ");
        Date start = new Date();
        shellSort.shell(arr1);
        Date end = new Date();
        long timediff = end.getTime() - start.getTime();
        System.out.println(timediff + "ms");
//        ArrayUtils.printArray(arr1);
    }

    /**
     * 希尔排序，希尔排序是一种插入排序，只不过对排序序列进行了分组排序，又称为缩小增量排序
     * 主要思想为，将序列按某一增量分组，每组内元素索引差就为该增量值
     * 如增量为3，则0、3、6、9这四个元素为一组，1、4、7、10这个四个元素为一组
     *
     * 先按增量分组对每组内元素进行简单插入排序
     * 然后，缩小增量，再进行简单插入排序
     * 当增量缩小为1的时候，就变成全序列的简单插入排序
     * 随着增量的减小，整个序列逐渐有序，因此，排序越来越快
     *
     * 对于增量的选择，如果选为偶数并且按一半缩减，可能导致序列中奇数位置的元素和偶数位置的元素直到最后一个增量排序才会交换位置
     * 因此，增量缩减一般不对半缩减，而是按照 increment = increment / 3 + 1 的方式缩减，且初始增量一般选为序列长度
     *
     * @param arr
     */
    public void shell(int[] arr) {
        int increment = arr.length;
        do {
            increment = increment / 3 + 1;
            for (int i = increment; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - increment;
                // 增量分组，因此j 按增量缩减
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + increment] = arr[j];
                    j -= increment;
                }
                arr[j + increment] = tmp;
            }

        } while (increment > 1);
    }
}
